#pragma once
#include <vector>
#include <map>
#include <string>
#include <queue>
#include<unordered_map>
#include <functional>
#include <algorithm>
#include <iostream>
#include <assert.h>
#include<list>
#include<iostream>

using namespace std;

class LRUCache{
public:
    LRUCache(int capacity)
        :capacity_(capacity)
    {}

    int get(int key){
        auto it=mp.find(key);
        //如果有该数据，就加入到头位置
        if(it!=mp.end()){
            //得到链表的迭代器
            auto list_iter=it->second;
            pair<int,int> listvalue=*list_iter;
            data.erase(list_iter);
            data.push_front(listvalue);
            mp[key]=data.begin();
            return listvalue.second;
        }
        //如果没有数据,返回-1
        else{
            return -1;
        }
    }


    void set(int key,int value){
        auto it=mp.find(key);
        if(it!=mp.end()){
            //如果已经有了key,更新数据,然后将其放在最前面
            auto list_iter=it->second;
            pair<int,int> list_value=*list_iter;
            list_value.second=value;
            data.erase(list_iter);
            data.push_front(list_value);    
            //更新Hash表
            mp[key]=data.begin();
        }
        //如果没有key,就需要判断容量
        //如果当前数量超过容量，就删除最后一个，负责之间在头添加即可
        else{
            if(data.size()>=capacity_){
               auto list_back=data.back();
               mp.erase(list_back.first);
               data.pop_back();
            }
            //向头部添加make_pair(key,value);
            data.push_front(make_pair(key,value));
            mp[key]=data.begin();
        }
    }
    //插入
private:
    unordered_map<int,list<pair<int,int>>::iterator> mp;
    //List存放一共K-Value类型的数据
    list<pair<int,int>> data;
    size_t capacity_;
};